package com.s3.stack;

/*基于链表实现的栈 */
public class LinkedStack {

	private static class Node {
		public Object data;
		public Node next;
	}

	protected static final int DEFAULT_LENGTH = 100;

	// 栈的容量
	protected int length = 0;

	// 栈中元素个数
	protected int used = 0;

	private Node headNode = null;

	public LinkedStack() {
		this(DEFAULT_LENGTH);
	}

	public LinkedStack(int length) {
		this.length = length;
	}

	// 栈的大小
	public int getLength() {
		return this.length;
	}

	// 每次都会更改 head 指针的位置
	public boolean push(Object value) {
		if (this.used >= getLength()) {
			return false;
		}
		// 创建新节点，并更新 head 指针的位置
		Node newNode = new Node();
		newNode.data = value;
		newNode.next = this.headNode;
		this.headNode = newNode;
		this.used++;
		return true;
	}

	// 出栈（删除节点）更倾向于 head 后移一位，而不是 tail 前移一位。因为如果要删除尾部节点且采用单链表接口则需要首先查找倒数第二个节点才能进行操作
	public Object pop() {
		if (this.used <= 0) {
			return null;
		}
		// 清空 head 所指向节点的信息，并后移一位，
		this.used--;
		Object ret = this.headNode.data;
		Node nextNode = this.headNode.next;
		this.headNode.data = null;
		this.headNode.next = null;
		this.headNode = nextNode;
		return ret;
	}

	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append("linkedStack = ");
		Node p = this.headNode;
		while (p != null) {
			stringBuilder.append(p.data + " ");
			p = p.next;
		}
		return stringBuilder.toString();
	}
	
	public boolean isEmpty() {
		return this.used == 0;
	}
	
	public void clear() {
		for(int i = 0; i < this.used; i++) {
			this.pop();
		}
	}
	
	public Object getTopData() {
		if (this.used <= 0) {
			return null;
		}
		return this.headNode.data;
	}
	
	public int getUsedLength() {
		return this.used;
	}

	public static void main(String[] args) {
		LinkedStack stack = new LinkedStack(3);
		System.out.println(stack.push(1));
		System.out.println(stack.push(2));
		System.out.println(stack.push(3));
		System.out.println(stack.push(5));
		System.out.println(stack);

		System.out.println(stack.pop());
		System.out.println(stack);

		System.out.println(stack.pop());
		System.out.println(stack);
	}

}
